/**
 * @file main.cpp
 * @author ikun (gitee.com/ikun-ikun)
 * @brief a testing programme of the BST
 * @version 0.1
 * @date 2022-10-15
 * 
 * @copyright Copyright (c) 2022
 * 
 */

#include<iostream>
#include "BinarySearchTree.h"
#include <vector>
#include<cstdlib>
#include<ctime>

/**
 *Print all the elements in the vector in order.
 */
template<typename Comparable>
void PrintVector(vector<Comparable> &_arr)  
{
    for(auto & x: _arr)
        cout << x<<" ";
    cout << endl;
}

    
/**
* Internal method to output the element into
*  the vector by infix traversal.
*/
template<typename Comparable>
void BinarySearchTree<Comparable>::InfixOutput(BinaryNode * & t ,vector<Comparable> &_sub)
{                                
    if(t==nullptr)
        return;
    InfixOutput(t->left,_sub);
    _sub.push_back(t->element);
    InfixOutput(t->right,_sub);
}

/** 
 * Call to disrupt the order of the vector.
 */
template<typename Comparable>
void Disorder(vector<Comparable> &_arr)         
{
    srand(time(nullptr));
    for(int i=0;i<_arr.size();i++)
    {
        swap(_arr[i], _arr[rand()%(_arr.size())]);
    }
}

/**
 * Sort the vector with disordering first when _mode
 * is 1. Sort the vector without disordering when 
 * _mode is 0. Show error when _mode is other value.
 * Functions in ctime file calls in this function
 * to record the time cost of the sorting process.
 */
template<typename Comparable>
void BinarySearchTree<Comparable>::BSTSorting(vector<Comparable> &_arr, int _mode)
{                                             
    clock_t begin;
    clock_t end;
    if(_mode==1)
        Disorder(_arr); 
    else if(_mode!=0)
    {
        cerr<<"wrong input!"<<endl;
        exit(-1);
    }
    begin=clock();
    for(auto & x:_arr)
        this->insert(x);
    vector<Comparable> sub;
    this->InfixOutput(root,sub);
    end=clock();
    cout<<"the sorting process takes "<<end-begin<<endl;
    swap(sub,_arr);
}
int main()
{
    /**
     * Object Groot is constructed to test
     * function Disorder and function
     * BSTSorting.
     * 
     */
    /*BinarySearchTree<int>Groot;
    vector<int> a;
    for(int i=0;i<10;i++)
        a.push_back(i);
    Disorder(a);
    PrintVector(a);
    Groot.BSTSorting(a);
    PrintVector(a);*/

    /**
     * Object GiantTree is constructed to
     * test the sorting effeciency in 
     * different situations.
     * 
     */
    BinarySearchTree<int> GiantTree;
    vector<int> b;
    int mode,j;
    cin >> mode;
    if(mode==0)
        j=50000;
    if(mode==1)
        j=5000000;
    for(int i=0;i<j;i++)
        b.push_back(i);
    GiantTree.BSTSorting(b,mode);
        
}
